from node import Node, SingleLinkList


def quick_sort(arr, left, right):
    """ 快排 """
    while left >= right:
        return
    i = left
    j = right
    key = arr[i]
    while i < j:
        while i < j and arr[j] >= key:
            j -= 1
        arr[i] = arr[j]
        while i < j and arr[i] <= key:
            i += 1
        arr[j] = arr[i]
    arr[i] = key
    quick_sort(arr, left, i-1)
    quick_sort(arr, i + 1, right)


def binary_search(arr, target):
    """ 折半查找 """
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = left + int((right - left) / 2)
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            right = mid - 1
        elif arr[mid] < target:
            left = mid + 1

    return -1


def binary_search_left(arr, target):
    """ 折半查找左侧边界 """
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = left + int((right - left) / 2)
        if arr[mid] == target:
            # 收缩右侧边界
            right = mid - 1
        elif arr[mid] > target:
            right = mid - 1
        elif arr[mid] < target:
            left = mid + 1

    if(left == len(arr) or arr[left] != target):
        return -1

    return left


def binary_search_right(arr, target):
    """ 折半查找右侧边界 """
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = left + int((right - left) / 2)
        if arr[mid] == target:
            # 收缩左侧边界
            left = mid + 1
        elif arr[mid] > target:
            right = mid - 1
        elif arr[mid] < target:
            left = mid + 1

    if(right < 0 or arr[right] != target):
        return -1

    return right


def find_1_char(str):
    """ 查找字符串中第一次只出现一次的字符 """
    # 构造哈希表并初始化
    hashMap = []
    i = 0
    while i < 256:
        hashMap.append(0)
        i += 1

    # 将hashMap内对应的值+1
    for c in str:
        hashMap[ord(c)] += 1

    for i in range(len(hashMap)):
        if hashMap[i] == 1:
            return chr(i)


def merge_arr(arr1, arr2):
    """ 合并两个有序数组 """
    i, j = 0, 0
    result = []
    while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1

    while i < len(arr1):
        result.append(arr1[i])
        i += 1

    while j < len(arr2):
        result.append(arr2[j])
        j += 1

    return result


def isValid(str):
    """ 是否是正确的字符串 """
    stack = []
    map = {')': '(', ']': '[', '}': '{'}
    for c in str:
        if c not in map:
            stack.append(c)
        elif not stack or map[c] != stack.pop():
            return False
    return not stack


def reverse_num(num: int):
    """ 翻转整数 """
    result = 0
    while(1):
        lastNum = num % 10
        num = int(num / 10)
        result = result * 10 + lastNum
        if num == 0:
            break
    return result


def reverse_str(str):
    """ 翻转字符串 """
    # 先转为字符数组
    strList = []
    for c in str:
        strList.append(c)

    left = 0
    right = len(strList) - 1

    while left < right:
        temp = strList[left]
        strList[left] = strList[right]
        strList[right] = temp
        left += 1
        right -= 1
    # 字符数组转字符串
    return ''.join(strList)


def single_num(arr):
    """ 找出数组中只有一个不同的数 """
    a = 0
    for obj in arr:
        a = a ^ obj
    return a


def f(n):
    """ 青蛙跳台阶（同斐波那契数列思想） """
    if n == 1:
        return 1
    if n == 2:
        return 2
    else:
        return f(n - 1) + f(n - 2)


def isAnagram(str1, str2):
    """ 是否相同字母异序 """
    dic1 = {}
    dic2 = {}
    for c in str1:
        dic1[c] = dic1.get(c, 0) + 1
    for c in str2:
        dic2[c] = dic2.get(c, 0) + 1
    return dic1 == dic2


def main():
    # UT
    arr = [1, 8, 5, 2, 1, 5, 6, 3, 1, 8, 9]
    print(arr)

    # sort
    quick_sort(arr, 0, len(arr) - 1)
    print(arr)

    # search
    r1 = binary_search(arr, 5)
    print(r1)

    r2 = binary_search_left(arr, 5)
    print(r2)

    r3 = binary_search_right(arr, 5)
    print(r3)

    c = find_1_char('aabbcdde')
    print(c)

    result = merge_arr([1, 2, 3], [1, 1, 11, 22, 33, 44])
    print(result)

    valid = isValid('(([[]])')
    print(valid)

    num = reverse_num(12345)
    print(num)

    strResult = reverse_str('abcde')
    print(strResult)

    singleNum = single_num([1, 1, 2, 2, 3, 4, 4])
    print(singleNum)

    for i in range(1, 20):
        print(f(i))

    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(3)
    node4 = Node(4)
    node5 = Node(5)

    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5
    node5.next = None

    obj = SingleLinkList(node1)
    obj.printAll()
    print(obj.is_has_cycle(node1))
    obj.reverse(node5)
    obj.printAll()

    print('---isAnagram')
    print(isAnagram('art', 'rat'))
    print('---isAnagram')


if __name__ == "__main__":
    main()
